package math;

import org.junit.Test;

import java.util.Arrays;

public class SuperPow372 {
    @Test
    public void test1() {
        superPow(2, new int[]{3});
        superPow(2, new int[]{1,0});
        superPow(1, new int[]{4,3,3,8,5,2});
        superPow(2147483647, new int[]{2,0,0});
    }

    final int base = 1337;
    public int superPow(int a, int[] b) {
        int x = 1;
        for (int i = 0; i < b.length; i++) {
            x = powerWithMod(x, 10);
            int y = powerWithMod(a, b[i]);
            x = ((x % base) * (y % base)) % base;
        }
        System.out.format("a: %d, b: %s, result: %d\n", a, Arrays.toString(b), x);
        return x;
    }

    public int powerWithMod(int x, int p) {
        if (p == 0) {
            return 1;
        }
        if (p == 1) {
            return x;
        }
        if (p % 2 == 0) {
            int t = powerWithMod(x, p/2);
            t = t % base;
            return (t * t) % base;
        } else {
            int t = powerWithMod(x, p-1);
            return (t % base) * (x % base) % base;
        }
    }
}
